Sheet materials such as paper and film are manufactured industrially as large reels. These large reels are characterised by their width and their length. In a separate industrial process from the manufacture of the reels of sheet material, the large reels are cut into smaller reels for use in variety of applications. The smaller reels are all cut to the same length but differ in width due to different applications requiring different widths of the material.
A commercially available industrial machine for cutting a large reel of material into smaller reels is the Atlas CW1040 Series Primary Slitter Rewinder.
The cutting process of the large reel from the manufacturing process into smaller reels is dependent on what the present demand for each of the widths of the smaller reels is. Accordingly, the machine needs to be configured prior to each and every cutting operation in order for appropriate quantities of each of the differing widths of smaller reels of material to be produced. During a cutting operation, knives of the cutting machine are arranged to simultaneously cut the material from the large reel into a plurality of reels of material with smaller widths. The arrangement of the knives to cut material from a large reel into a plurality of smaller reels is referred to as a pattern. Each of the smaller reels is cut to the same length. A cutting pattern is therefore repeatedly used in a cutting operation until the desired quantity of smaller reels of particular widths has been produced. The cutting pattern is then changed so that smaller reels of different widths can be produced from the same large reel.
A cutting operation of a single large reel of material into a plurality of smaller reels will typically require about 25 different patterns but may require up to 80 patterns or more. In order to change between patterns during a cutting operation, it is necessary to stop the operation of the cutting machine and then for the knife positions to be manually changed by machine operators. The changing of patterns, i.e. the knife positions, is therefore a slow process that reduces the efficiency of the cutting operation.
When configuring a cutting machine prior to a cutting operation, a plurality of patterns need to be calculated to ensure that the desired quantities of smaller reels will be produced. The primary consideration when determining the patterns is usually to minimise wastage of the material being cut. An important further consideration is to reduce the number of patterns required in order to reduce the inefficiency caused by pattern changes.
The generation of patterns with the specific goal of minimising wastage of the material is referred to as the one-dimensional cutting stock problem, 1D-CSP. The problem is one dimensional due to the variable nature of the widths of the smaller reels. It is not a two dimensional problem as the lengths of the smaller reels is fixed. Finding and improving solutions to the 1D-CSP is an old mathematical problem that is a subject of continued research. It is well known that the 1D-CSP is quite degenerate, i.e. multiple different solutions with the same waste often exist. This can be explained by geometrical re-arrangement, i.e. it is sometimes possible, for example, to swap two items belonging to different patterns, creating new patterns in the process.
The pattern reduction problem is treated as an independent problem from the 1D-CSP. That is to say, after patterns that are a solution to the 1D-CSP have been found in order to minimise wastage of the material being cut, a separate process is performed to reduce the number of patterns. The pattern reduction problem is a harder problem to solve than the 1D-CSP. The problem has been shown to be to be NP-hard. In Aldridge, C. et al., Pattern Reduction in Paper Cutting. European Study Group with Industry, (pp. 1-15). Oxford, 1996, a special class of the 1D-CSP is considered where each pattern contains at most two items. For this class, the first-fit-decreasing rule gives an optimal answer to the minimum waste problem. So, the waste minimisation problem is easy. However, the corresponding pattern minimisation problem for this class has been shown to be strongly NP-hard. Part of the difficulty of the pattern minimisation problem is that good lower bounds are difficult to find. If the number of different widths of smaller reels, i.e. item sizes, is d, linear programming indicates that there will be approximately d patterns in an optimal solution to the 1D-CSP. However, trivial examples can be constructed where d distinct sizes have a one-pattern minimum waste solution. This process generalises so that for any m, 1≤m≤d, examples can be produced where the minimum waste solution has no more than m patterns. FIG. 1 shows the construction for m=2: Also, only one easy lower bound is known in the literature; this adds one instance of each item and divides the sum by the master size. For the above example, this bound is 2, regardless of p & q. This trivial lower bound, is so weak in practice as to be almost useless. Alves, C. et al., New lower bounds based on column generation and constraint programming for the pattern minimization problem, Computers & Operations Research, 2944-2954, 2009, provides stronger bounds based on a combination of column generation and constraint programming. However, these are non-trivial to implement, even in the absence of additional practical constraints.
Three broad approaches are known for minimising the number of patterns. The first approach controls the number of patterns during the solution of the 1D-CSP. Within this class, one sub-approach solves a multi-objective optimisation problem, see for example: Haessler, R. W., Controlling Cutting Pattern Changes in One-Dimensional Trim Problems. Operations Research, 483-493, 1975; Moretti, A. C., & Neto, L. D., Nonlinear Cutting Stock Problem to Minimize the Number of Different Patterns and Objects. Computational & Applied Mathematics, 1-18, 2008; Cerqueira, G. R., & Yanasse, H. H., A pattern reduction procedure in a one-dimensional cutting stock problem by grouping items according to their demands. Journal of Computational Interdisciplinary Sciences, 159-164, 2009; Kallrath, J., Rebennack, S., & Kallrath, J., Solving real-world cutting stock-problems in the paper industry: Mathematical approaches, experience and challenges. European Journal of Operational Research, 374-389, 2014; and Sykora, A. M., Potts, C., Hantanga, C., Goulimis, C. N., & Donnelly, R., A Tabu Search Algorithm for a Two-Objective One-Dimensional Cutting Stock Problem. 12th ESICUP Meeting. Portsmouth, 2015. Whilst powerful, these face two challenges: (a) determining robustly the trade-off of waste vs. pattern count and (b) implementing the various practical pattern constraints is difficult and sometimes impossible.
The second approach uses an exact optimisation algorithm to solve a suitable integer programming formulation, which can range from a mixed-binary/integer formulation with a generic commercial solver to custom advanced algorithms, see for example: Vanderbeck, F., Exact Algorithm for Minimising the Number of Setups in the One-Dimensional Cutting Stock Problem. Operations Research, 915-926, 2000; and Belov, G., & Scheithauer, G., The number of setups (different patterns) in one-dimensional stock cutting. Dresden: Department of Mathematics, Dresden University of Technology, 2003. Although this approach can deliver improvements, it remains computationally demanding for practical problems, in particular for solutions that require more than 25 patterns.
The complexity of the first and second approaches described above, require respective computation times of 2 hours and ½ hour or longer. Even allowing for improvements in hardware such computation times are not acceptable. For example, an order may be changed at the last minute and a substantially instantaneous recalculation of the patterns will be required. Moreover, the inclusion of the practical constraints is problematic.
The third approach involves taking an existing minimum waste solution and then applying a series of fast transformations, each of which maintains the original order allocation and run length (and therefore the waste), but reduces the pattern count. These are transformation heuristics. The first such heuristic, referred to as the 2:1 rule, was described in Johnston, R. E., Rounding algorithms for cutting stock problems. Asia Pacific Journal of Operations Research, 166-171, 1986. This provides necessary and sufficient conditions for two patterns to be combined into one. The pattern reduction is calculated from specific detected conditions.
This was followed by the staircase heuristic as described in Goulimis, C. N., Optimal solutions for the cutting stock problem. European Journal of Operational Research, 197-208, 1990. This looks for pattern triplets of the form shown in FIG. 2A. In FIG. 2A, the labelled blocks each contain one or more of the required items. This form can be transformed to that shown in FIG. 2B subject to the new pattern (consisting of A+D) being feasible. In FIGS. 2A and 2B there is therefore a transformation of three patterns into two. The pattern reduction is achieved by searching for better solutions that may or may not exist.
These two heuristics, which both require trivial computational effort, can be applied exhaustively to any starting solution until no further improvement can be found. Their usefulness in practice is immense. There are situations in which a minimum waste solution with 28 patterns is reduced by the 2:1 rule to 26 patterns. Applying the staircase heuristic reduces the number of patterns to just 9.
Over the years additional transformation heuristics have been published, culminating in the KOMBI family in Foerster, H., & Wascher, G., Pattern reduction in one-dimensional cutting stock problems. International Journal of Production Research, 1657-1676, 2000. This looks at triples and quadruples and applies a recursive procedure. All the transformation heuristics published so far have the same structure, they examine subsets of cardinality s where s depends on the heuristic and 2≤s≤5. Each may be embedded in a parallelisable loop that examines potentially all (sn)=O(ns) combinations for a starting solution with n patterns. This poses a computational challenge when the number of initial patterns starts exceeding 50. For example, (550)≈2 million quintuples.
Transformation heuristics offer the following advantages over the other approaches:                The waste and allocation aspects of the starting solution remain unchanged;        They can easily accommodate practical constraints; and        They are not computationally demanding and therefore generate improvements very quickly.        
Although transformation heuristics are valuable in reducing the pattern count, they remain severely suboptimal. All known transformation heuristics involve examining small subsets of the solution patterns, with cardinality up to 4 or 5.
In addition, solutions need to be found that are consistent with practical constraints. There are very many different pattern constraints because the machinery for cutting, and operation of the machinery, is by no means standardised. Common practical constraints include:
1. Minimum width: patterns of total size below a user-specified minimum are unacceptable.
2. Knives: the maximum number of items in a pattern is constrained by the number of available slitting knives.
3. Small/big items: the user defines certain items as small/big and places constraints on the minimum/maximum number of instances of each class.
4. Occurrences: each item may have restrictions on the number of times it appears in each pattern. The most common of these is the multi-pack constraint, where the occurrences must be a multiple of a user-specified value (e.g. the pattern can contain 0/3/6/ . . . instances of an item, but 1 or 4 occurrences are not allowed).
5. Distinct: patterns may not contain items with similar size; this is encountered in situations where knife placement or labelling is manual and operators cannot be relied on to distinguish very similar sizes.
6. Minimum pattern multiplicity: in some cases there is a minimum run length for each pattern.
A related consideration is that machine operators particularly dislike singleton patterns that are only used once. Given two solutions with same overall pattern count, the one with the fewest singleton patterns is therefore preferable.
These constraints create difficulties in column generation and other decomposition algorithms for the main 1D-CSP. It is no longer sufficient to solve a pure knapsack as the auxiliary problem. The constraints cause the same difficulties in the pattern minimisation.
Transformation heuristics are not only computationally efficient but are appropriate for finding solutions to practical constraints such as those listed above. Accordingly, known approaches to generating patterns for use in a cutting operation first calculate a solution that minimises the wastage of the material being cut and then apply the above-described transformation heuristics to reduce the pattern count.
There is a need to improve known techniques for generating patterns for use in a cutting operation.